1. Field of the Invention
This invention relates generally to the field of data exchange. More specifically, this invention relates to data exchange among a plurality of agents using a plurality of data links, each data link passing through or including a crossbar.
2. Background
Those of ordinary skill in the art will realize that, in its most basic form, data exchange can represent the transfer of data of a communication from a transmitting agent to a receiving agent over a single dedicated data link. In a slightly more complicated form, data exchange can represent the transfer of data from agent A to agent B over dedicated data link 1 and the transfer of data from agent B to agent A over dedicated data link 2. Alternatively, data exchange can represent the transfer of data from agent A to agent B over a dedicated data link at time 1 and the transfer of data from agent B to agent A over the same dedicated data link at time 2 where time 1 and time 2 are different times such that the two transmissions do not conflict with one another. In its most abstract form, data exchange can represent the transfer of data from n transmitting agents to n receiving agents over n data links where n is an positive integer. As the number of agents and data links grows, the complexity and cost of the data exchange system can become extreme.
One method for simplifying the data exchange system is to combine the data links rather than have separate links between each of the agents. This can be accomplished by connecting each of the agents only to a common point or crossbar (XBAR) which connects the agents two at a time as appropriate to complete the data link between the agents. This method benefits from a reduction in the number of data links in the data exchange system but suffers from an increase in traffic over each of the data links. Those of ordinary skill in the art will realize that each of the data links has a limited bandwidth depending on the transmission media. Eventually, each of the data links will reach this limit and will not be able to transmit any more data at any faster speeds.
Some terminology which will be used herein will now be set forth. The term “Switch Fabric” describes a plurality of Data Links interconnecting Agents through Packet Switching Crossbars (“XBARs”). The Switch Fabric can be constructed using one or more XBARs. Each “Agent” can transmit or receive data over the Switch Fabric. An Agent which is involved in a data transfer in which it is transmitting is called the “Transmitting Agent”. Likewise, an Agent which is involved in a data transfer in which it is receiving is called the “Receiving Agent”. Agents and XBARs connect to Data Links using “Data Link Ports”. An Agent has as many Data Link Ports as there are XBARs in the system. An XBAR has as many Data Link Ports as there are Agents in the system.
The data which is transferred between Agents is called a “Stream of Packets” and each of the packets will be of arbitrary size. The Stream of Packets is comprised of one or more “Flows”. A “Flow” is a group of packets that are related, i.e., they are commonly addressed. An “Order Critical Flow” is a Flow which is order sensitive, i.e., the order of this group of packets needs to be maintained when being transferred over the Switch Fabric. Such order must be maintained, for example, in voice over packet communications and video over packet communications, to name two examples.
Each Transmitting Agent keeps a queue of packets to be transmitted in a Transmit Queue (“TQ”) or transmit buffer. Each Transmitting Agent keeps queues of packets for each Data Link of the Switch Fabric. These are called Transmit Link Queues (“TLQs”). A Transmitting Agent's packets to be transmitted are removed from its TQ and assigned to its plurality of TLQs and then transmitted over the Data Link(s).
Each Receiving Agent keeps a queue of packets received from each Data Link of the Switch Fabric. These are called Receive Link Queues (“RLQs”). Each Receiving Agent keeps a queue of packets received in a Receive Queue (“RQ”) or receive buffer. A Receiving Agent's received packets are removed from its plurality of RLQs to its RQ as the received packets are received.
Packets which pass between agents across the switch fabric can be separated into two groups: those for which order must be maintained and those whose order can be modified by the switch fabric. As was previously mentioned, the former group is defined to be an Order Critical Flow while the latter is defined simply as a Flow. There are numerous reasons why an Order Critical Flow might exist in a system. One might be that the flow is comprised of packets of digitized video or audio. In this case, it is highly desirable to keep all packets of this flow in sequential order. Out of order packets would introduce distortions in what is supposed to approximate a continuous signal. This is just one example of an Order Critical Flow; there are many others. The present invention addresses the issue of maintaining packet ordering for Order Critical Flows regardless of the reason for the requirement for preservation of packet order.